class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        // 前缀积+后缀积
        int sz = nums.size();
        vector<int> dp1(sz + 1, 1), dp2(sz + 1, 1), ret(sz);
        for(int i = 1; i <= sz; ++i)
        {
            dp1[i] = dp1[i - 1] * nums[i - 1];
        }
        for(int i = sz - 1; i >= 0; --i)
        {
            dp2[i] = dp2[i + 1] * nums[i];
        }
        for(int i = 0; i < sz; ++i)
        {
            ret[i] = dp1[i] * dp2[i + 1];
        }
        return ret;
    }
};